package com.leetcode;

import java.util.Arrays;
import java.util.List;

/**
 * 三数之和：给你一个包含 n 个整数的数组nums，判断nums中是否存在三个元素 a，b，c ，
 * 使得a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
 *
 * 解法：
 * ①：将数组排序
 * ②：先固定一个值，将问题转换为两数之和，可以利用双指针
 *    具体实现：（三指针）
 *    1. k 指向第一个值，然后k不动
 *    2. i 指向 k 的下一个值，j 指向最后一个值
 *    原理：sum = n[k] + n[i] + n[j]
 *      如果 sum<0, k 和 j 不动，要使n[k] + n[i] + n[j]=0，则i指向的值要变大，因为数组是排序的，则i指向下一个值
 *      即：sum < 0, j不动，i指向下一个值（i++）
 *          sum > 0，i不动，j指向上一个值（j--），原理同 sum<0 时一样的分析
 *      如果sum = 0，保存n[k]、n[i]、n[j]三个值，同时i指向下一个值（i++），j指向上一个值（j--）
 *    直到 i >= j，k 的第一遍循环结束，k++ 回到1.
 *
 * 整个过程保存的n[k]、n[i]、n[j]三个值都是不重复的。（画图比较清晰）
 *
 * 另外：当 k i j 三个指针需要变化时（k++、i++、j--),有可能下一个跟原来的值相等，
 * 这样我们可以不用再做一遍计算，可以直接排序，所以，当下一个值是相等的时候，直接再指向下一个
 * 可这样写：" while(n[i] == n[++i]); ",这是一个没有循环体的循环语句，注意最后面有分号
 *      不管 i 的下一个值跟现在的值是否相等，i都会加1
 *      比如说：[1,1,1,1,1,2]中，现在i指向第一个1，执行while(n[i] == n[++i]);后，i会指向 2
 * 所以同理：j可以这样：while(n[j] == n[--j])，然后再加判断条件：while(i < j && nums[j] == nums[--j]);
 * k 这样写：while(k < length - 2 && nums[k] == nums[++k]);
 * 都可以保证当下一个值是相等的时候，可以不用再计算
 */
public class ThreeSum {
    public static void main(String[] args) {
        int[] arr = new int[]{-1,0,1,2,-1,-4,-2,-3,3,0,4};
        System.out.println(Arrays.toString(arr));
        Solution s = new Solution();
        List<List<Integer>> lists = s.threeSum(arr);
        System.out.println(lists);
    }
}

